// 题目：https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c?tpId=13&tqId=634&ru=%2Fpractice%2Fa861533d45854474ac791d90e447bafd&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
// 思路1：1.前序遍历-递归实现；2.前序遍历到叶子节点的时候，比较当前路径的和与期望值比较；
         //3.如果不是叶子节点，则继续遍历比较；

#include <algorithm>
#include <climits>
#include <queue>
#include <vector>
#include <stack> 
#include <limits>

using namespace std;
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return bool布尔型
     */
    std::vector<std::vector<int> > t_vec_vec;
    std::vector<int> t_vec;
    void FindPath(TreeNode* root, int cur_sum, int expect_sum) {

        if (root->left == nullptr && root->right == nullptr) {
            auto leaf_sum = root->val + cur_sum;
            if (leaf_sum == expect_sum) {
                t_vec.push_back(root->val);
                t_vec_vec.push_back(t_vec);
                t_vec.pop_back();
            }
            return;
        }

        t_vec.push_back(root->val);
        if (root->left) {
            FindPath(root->left, root->val + cur_sum, expect_sum);
        }

        if (root->right) {
            FindPath(root->right, root->val + cur_sum, expect_sum);
        }
        t_vec.pop_back();
    }
    std::vector<std::vector<int> > FindPath(TreeNode* root, int sum) {
        // write code here
        if (root == nullptr) return t_vec_vec;
        FindPath(root, 0, sum);
        return t_vec_vec;
    }
};


